package _dp

import org.junit.Assert
import org.junit.Test

/**
 *
 * https://leetcode.cn/problems/house-robber/description/
 * https://blog.csdn.net/2303_79786049/article/details/141503133
 *
 * 题型： 动态规划
 *
 * ```
 * 198. 打家劫舍
 *
 * 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
 * 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
 *
 * 示例 1：
 * 输入：[1,2,3,1]
 * 输出：4
 * 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
 *      偷窃到的最高金额 = 1 + 3 = 4 。
 *
 * 示例 2：
 * 输入：[2,7,9,3,1]
 * 输出：12
 * 解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
 *      偷窃到的最高金额 = 2 + 9 + 1 = 12 。
 *
 *
 * 提示：
 * 1 <= nums.length <= 100
 * 0 <= nums[i] <= 400
 * ```
 */
class leetcode_198 {
    @Test
    fun test_1() {
        val actual = rob(intArrayOf(1, 2, 3, 1))
        val expected = 4
        Assert.assertEquals(expected, actual)
    }

    @Test
    fun test_2() {
        val actual = rob(intArrayOf(2, 7, 9, 3, 1))
        val expected = 12
        Assert.assertEquals(expected, actual)
    }

    private fun rob(nums: IntArray): Int {
        /**
        题型: 动态规划
         */
        if (nums.size == 1) {
            return nums[0]
        }
        // 1 定义数组以及下标
        // 第i天，偷与不偷的最大值
        val dp: IntArray = IntArray(nums.size)
        // 2 确定递推公式: dp[i] = max(dp[i-1], dp[i-2] + num[i])

        // 3 确定 dp，以及初始化
        dp[0] = nums[0]
        dp[1] = Math.max(dp[0], nums[1])

        // 4 遍历顺序
        for (i in 2 until nums.size) {
            // 第i天不偷：dp[i-1]
            val v1 = dp[i - 1]
            // 第i天偷：dp[i-2] + num[i]
            val v2 = nums[i] + dp[i - 2]
            dp[i] = Math.max(v1, v2)
        }
        // 5 打印数组
        println(dp.contentToString())
        return dp.last()
//        return dp[nums.size - 1]
    }
}